package 代码随想录.数组.二分查找;

/**lc704 二分查找
 * link：https://leetcode-cn.com/problems/binary-search/
 * @author ChenweiLin
 * @create 2021-11-28 18:26
 */
public class binarySearch {
    public static void main(String[] args) {
        //测试用例
        int[] nums = new int[]{-1,0,3,5,9,12};
        System.out.println(search(nums, 2));
    }
        public static int search(int[] nums, int target) {
            //二分查找模板
            //特殊情况：如果在界外，直接返回-1
            if(nums[0] > target || target >nums[nums.length-1])
                return -1;

            int left = 0,right = nums.length-1;//左右边界

            while (left <= right){//只要左边界仍小于右边界 进行查找
                int middle= left + ((right - left / 2));//放置left + right 越界 todo 指针放置的位置很重要 必须在while循环里创建
                if (target == nums[middle]){
                    return middle;
                }else if(target > nums[middle]){
                    left = middle + 1;
                }else if(target < nums[middle]){
                    right = middle -1;
                }
            }
            //找完了仍然没找到
            return -1;

        }
}